package lc;

import java.util.Arrays;

import org.junit.Test;

import util.BracketUtils;

public class Ex498 {
    class Solution1 {
        public int[] findDiagonalOrder(int[][] mat) {
           if (mat == null) return new int[0];
           int m,n;
           if ((m = mat.length) == 0 || (n = mat[0].length) == 0) return new int[0];
    
        //    int left = 0, up = 0, down = m - 1, right = n - 1;
            int lefti = 0, leftj = 0, idx = 0, righti = 0, rightj = 0;
            boolean flag = true;
            int[] res = new int[m * n];
            while (true) {

                    if (flag) {
                        for (int i = lefti, j = leftj; i >= 0 && j < n; i--, j++) {
                            res[idx++] = mat[i][j];
                        }
                    } else {
                        for (int i = righti, j = rightj; i < m && j >= 0; i++, j--) {
                            res[idx++] = mat[i][j];
                        }
                    }
                    flag = !flag;
                    if (lefti < m - 1) {
                        lefti++;
                        leftj = 0;
                    } else {
                        lefti = m - 1;
                        leftj = leftj == n - 1 ? n - 1 : leftj + 1;
                    }
                    if (rightj < n - 1) {
                        rightj++;
                        righti = 0;

                    } else {
                        rightj = n - 1;
                        righti = righti == m - 1 ? m - 1 : righti + 1;
                    }
                    if (idx == m * n) break;
                }
            return res;
        }
    }

    class Solution {
        public int[] findDiagonalOrder(int[][] mat) {
            int m = mat.length, n = mat[0].length;
            int li = 0, lj = 0, ri = 0, rj = 0, i, j ;
            boolean leftToRight = true;
            int[] res = new int[m * n];
            int idx = 0;
            while (idx < res.length) {
                if (leftToRight) {
                    i = li;
                    j = lj;
                    while (i >= ri && j <= rj) {
                        res[idx++] = mat[i][j];
                        i--;
                        j++;
                    }
                } else {
                    i = ri;
                    j = rj;
                    while (i <= li && j >= lj) {
                        res[idx++] = mat[i][j];
                        i++;
                        j--;
                    }
                }
                leftToRight = !leftToRight;
                lj = li == m - 1 ? lj + 1 : lj;
                li = li == m - 1 ? li : li + 1;
                ri = rj == n - 1 ? ri + 1 : ri;
                rj = rj == n - 1 ? rj : rj + 1;
                if (lj == n - 1 && ri == m - 1) {
                    res[idx++] = mat[ri][lj];
                    break;
                }
            }
            return res;
        }
    }
    @Test
    public void test() {
        Solution s = new Solution();
        int[][] mat = BracketUtils.to2DArray("[[1,2,3],[4,5,6],[7,8,9]]");
        System.out.println(Arrays.toString(s.findDiagonalOrder(mat)));
    }
}
